#include <stdio.h>
#include <string.h>
#include <math.h>
#define M 200000
int main()
{
	int a[M] = {0};
	int rec[M] = {0};
	int i, j, t, n;
	int x=10000000+9;
	int cc = 0;
	int all[1000];
	int flag;	//	0用来标记前面一位小于上一位
	// printf("%d", x);
	while(scanf("%d", &n) != EOF)
	{
		t = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		for(i = 1; i < n; i++)
		{
			flag = 0;
			if(a[i] > a[i-1])
			{
				flag = 1;
				rec[i] = rec[i-1] + i;
				// t += rec[i];
			}
			if(flag == 0)
			{
				for(j = i-2; j >= 0; j--)
					if(a[i] > a[j])
					{
						rec[i] = j + rec[j];
						break;
					}
			}
			// rec[i] = t;
			/*
			for(j = i-1; j >= 0; j--)
				if(a[i] > a[j]) t++;
			*/
		}
		// printf("%d\n", i);
		for (i = 0; i < n; i++)
			printf("%d\n", rec[i]);
		t = rec[n-1];
		t = t % x;
		all[cc] = t;
		cc++;
		// memset(a,0,sizeof(a));
	}
	for (i = 0; i < cc; i++)
		printf("%d\n", all[i]);
	return 0;
}
